{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Power Set LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #幂集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>幂集。编写一种方法，返回某集合的所有子集。集合中<strong>不包含重复的元素</strong>。</p>\n",
    "\n",
    "<p>说明：解集不能包含重复的子集。</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>： nums = [1,2,3]\n",
    "<strong> 输出</strong>：\n",
    "[\n",
    "  [3],\n",
    "&nbsp; [1],\n",
    "&nbsp; [2],\n",
    "&nbsp; [1,2,3],\n",
    "&nbsp; [1,3],\n",
    "&nbsp; [2,3],\n",
    "&nbsp; [1,2],\n",
    "&nbsp; []\n",
    "]\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [power-set-lcci](https://leetcode.cn/problems/power-set-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [power-set-lcci](https://leetcode.cn/problems/power-set-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res=[[]]\n",
    "        if not nums:\n",
    "            return res\n",
    "        for num in nums:\n",
    "            res+=[arr+[num] for arr in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[], ]\n",
    "        for num in nums:\n",
    "            res += [arr + [num] for arr in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        for i in nums:\n",
    "            for j in range(len(ans)):\n",
    "                ans.append(ans[j]+[i])\n",
    "                print(ans)\n",
    "            ans.append([i])\n",
    "        ans.append([])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        st = []\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(st[:])\n",
    "                return\n",
    "            dfs(i + 1)\n",
    "            st.append(nums[i])\n",
    "            dfs(i + 1)\n",
    "            st.pop()\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.ans = []\n",
    "        nums = sorted(nums)\n",
    "        def dfs(path, nums, idx, N):\n",
    "            self.ans.append(path)\n",
    "            for i in range(idx, N):\n",
    "                dfs(path + [nums[i]], nums, i+1, N)\n",
    "        dfs([], nums, 0, len(nums))\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = [[]] \n",
    "        for c in nums:\n",
    "            newres = []\n",
    "            for m in res:\n",
    "                newres.append(m+[c])\n",
    "            res += newres\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        v = [False]*n\n",
    "        \n",
    "        def bt(choose, x):\n",
    "            nonlocal ans\n",
    "            if x == n+1:\n",
    "                return\n",
    "            t = deepcopy(choose)\n",
    "            ans.append(t)\n",
    "            for i in range(x, n):\n",
    "                if not v[i]:\n",
    "                    choose.append(nums[i])\n",
    "                    v[i] = True\n",
    "                    bt(choose, i+1)\n",
    "                    choose.pop()\n",
    "                    v[i] = False\n",
    "        \n",
    "        bt([], 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        if not nums:\n",
    "            return res\n",
    "            \n",
    "        for num in nums:\n",
    "            res += [arr+[num] for arr in res]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        def dfs(path, index):\n",
    "            res.append(path)\n",
    "            for i in range(index, len(nums)):\n",
    "                dfs(path + [nums[i]], i + 1)\n",
    "\n",
    "        dfs([], 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        return [[nums[i] for i in range(n) if x >> i & 1] for x in range(1 << n) ]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 回溯安排\n",
    "        def dfs(pos,res):\n",
    "            if n == pos:\n",
    "                ans.append(res[:])\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(pos + 1,res)\n",
    "            # 选\n",
    "            res.append(nums[pos])\n",
    "            dfs(pos + 1,res)\n",
    "            res.pop()\n",
    "\n",
    "        n = len(nums)\n",
    "        nums.sort(reverse=False)\n",
    "        ans = list()\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        len_nums = len(nums)\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        self.res = []\n",
    "        self.path = []\n",
    "\n",
    "\n",
    "        def dfs(start_idx):\n",
    "            self.res.append(self.path[:])\n",
    "\n",
    "            for i in range(start_idx, len_nums):\n",
    "                self.path.append(nums[i])\n",
    "                dfs(i+1)\n",
    "                self.path.pop()\n",
    "\n",
    "\n",
    "        dfs(0)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\n",
    "        res = [[]]\n",
    "        for num in nums:\n",
    "            res += [_ + [num] for _ in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\n",
    "        res = [[]]\n",
    "        for num in nums:\n",
    "            res += [_ + [num] for _ in res]\n",
    "        return res\n",
    "\n",
    "\n",
    "        # each iteration in res for [1, 2, 3]\n",
    "        # num = 1, res = []\n",
    "        # []\n",
    "        # [1] \n",
    "        # num = 2, res = [], [1]\n",
    "        # [2]\n",
    "        # [1, 2]\n",
    "        # num = 3, res = [], [1], [2], [1, 2]\n",
    "        # [3]\n",
    "        # [1, 3]\n",
    "        # [2, 3]\n",
    "        # [1, 2, 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        s = set(nums)\n",
    "        # 初始结果列表\n",
    "        res = [[]]\n",
    "        # 遍历集合中的每一个元素\n",
    "        for i in s:\n",
    "            # 遍历当前结果列表，对每个子集，都尝试添加当前元素，形成新的子集\n",
    "            res += [curr + [i] for curr in res]\n",
    "            # 返回结果列表\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\n",
    "        res = [[]]\n",
    "        for num in nums:\n",
    "            res += [_ + [num] for _ in res]\n",
    "        return res\n",
    "\n",
    "        # I am just adding the new num in nums to the res for its num[:-1]\n",
    "\n",
    "\n",
    "        # each iteration in res for [1, 2, 3]\n",
    "        # num = 1, res = []\n",
    "        # []\n",
    "        # [1] \n",
    "        # num = 2, res = [], [1]\n",
    "        # [2]\n",
    "        # [1, 2]\n",
    "        # num = 3, res = [], [1], [2], [1, 2]\n",
    "        # [3]\n",
    "        # [1, 3]\n",
    "        # [2, 3]\n",
    "        # [1, 2, 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "\n",
    "        res = []\n",
    "        temp = []\n",
    "\n",
    "        def backtrack(start_index):\n",
    "            \n",
    "            res.append(temp[:])\n",
    "\n",
    "            \n",
    "            for i in range(start_index,len(nums)):\n",
    "                temp.append(nums[i])\n",
    "\n",
    "                backtrack(i+1)\n",
    "\n",
    "                temp.pop()\n",
    "        backtrack(0)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        result = []  # 存储结果的列表\n",
    "        def backtrack(start, subset):\n",
    "            result.append(subset[:])  # 将当前子集添加到结果列表\n",
    "            for i in range(start, len(nums)):\n",
    "                subset.append(nums[i])  # 将当前元素加入当前子集\n",
    "                backtrack(i + 1, subset)  # 递归调用，下一个元素从 i+1 开始\n",
    "                subset.pop()  # 回溯，将当前元素从当前子集中移除\n",
    "\n",
    "        backtrack(0, [])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = [[]] \n",
    "        for c in nums:\n",
    "            newres = []\n",
    "            for m in res:\n",
    "                newres.append(m+[c])\n",
    "            res += newres\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n=len(nums)\n",
    "        ans=[]\n",
    "        path=[]\n",
    "        def DFS(i:int)->None:\n",
    "            if i==n:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            #不选nums[i]\n",
    "            DFS(i+1)\n",
    "            #选nums[i]\n",
    "            path.append(nums[i])\n",
    "            DFS(i+1)\n",
    "            path.pop()#恢复现场？？？\n",
    "        DFS(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        def backtracking(start, lis):\n",
    "            res.append(lis[:])\n",
    "            if start == len(nums)-1:\n",
    "                return\n",
    "            for j in range(start+1, len(nums)):\n",
    "                lis.append(nums[j])\n",
    "                backtracking(j, lis)\n",
    "                lis.pop(-1)\n",
    "\n",
    "        for start in range(len(nums)):\n",
    "            lis = []\n",
    "            lis.append(nums[start])\n",
    "            backtracking(start, lis)\n",
    "        \n",
    "        res.append([])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans =[]\n",
    "\n",
    "        n = len(nums)\n",
    "        def dfs(nowi, nownums):\n",
    "            # print(nownums)\n",
    "            if nowi == n:\n",
    "                ans.append(copy.deepcopy(nownums))\n",
    "                return \n",
    "            dfs(nowi + 1, nownums)\n",
    "            nownums.append(nums[nowi])\n",
    "            dfs(nowi + 1, nownums)\n",
    "            nownums.pop()\n",
    "\n",
    "        dfs(0, [])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        def backtracking(start, lis):\n",
    "            \n",
    "            if start == len(nums)-1:\n",
    "                return\n",
    "            for j in range(start+1, len(nums)):\n",
    "                lis.append(nums[j])\n",
    "                # print(lis)\n",
    "                res.append(lis[:])\n",
    "                backtracking(j, lis)\n",
    "                lis.pop(-1)\n",
    "\n",
    "        for start in range(len(nums)):\n",
    "            lis = []\n",
    "            lis.append(nums[start])\n",
    "            \n",
    "            res.append(lis)\n",
    "            backtracking(start, lis)\n",
    "\n",
    "        res.append([])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        #回溯\n",
    "        res=[]\n",
    "        def backtrack(i,path):\n",
    "            res.append(path[:])\n",
    "            # path.append(nums[i])\n",
    "            # res.append(path)\n",
    "            for j in range(i+1,len(nums)):\n",
    "                path.append(nums[j])\n",
    "                backtrack(j,path)\n",
    "                path.pop()\n",
    "        backtrack(-1,[])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def backtracing(subset: List, res: List[List], cur_idx) -> None:\n",
    "            res.append(list(subset))\n",
    "\n",
    "            if cur_idx > len(nums)-1:\n",
    "                return \n",
    "            \n",
    "            for i in range(cur_idx, len(nums)):\n",
    "                subset.append(nums[i])\n",
    "                backtracing(subset, res, i+1)\n",
    "                subset.pop()\n",
    "        \n",
    "        res = []\n",
    "        backtracing([], res, 0)\n",
    "        # print(res)\n",
    "        return res \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "\n",
    "        def dfs(i=0):\n",
    "            if i < len(nums):\n",
    "                lr = len(res)\n",
    "                for j in range(lr):\n",
    "                    res.append(res[j] + [nums[i]])\n",
    "                dfs(i+1)\n",
    "        dfs()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def back(self,nums,result,path,used,startindex):\n",
    "        result.append(path[:])\n",
    "        for i in range(startindex,len(nums)):\n",
    "            if i>0 and nums[i]==nums[i-1] and used[i-1]==0:\n",
    "                continue\n",
    "            path.append(nums[i])\n",
    "            used[i]=1\n",
    "            self.back(nums,result,path,used,i+1)\n",
    "            path.pop()\n",
    "            used[i]=0\n",
    "            \n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        result=[]\n",
    "        path=[]\n",
    "        nums.sort()\n",
    "        used=[0]*len(nums)\n",
    "        self.back(nums,result,path,used,0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "       n = len(nums)\n",
    "       res = []\n",
    "       _list = []\n",
    "       def dfs(i: int) -> None:\n",
    "          if i == n:\n",
    "             res.append(_list.copy())\n",
    "             return\n",
    "          dfs(i + 1)\n",
    "          _list.append(nums[i])\n",
    "          dfs(i + 1)\n",
    "          _list.pop()\n",
    "       dfs(0)\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 初始结果列表\n",
    "        res = [[]]\n",
    "        # 遍历集合中的每一个元素\n",
    "        for i in nums:\n",
    "            # 遍历当前结果列表，对每个子集，都尝试添加当前元素，形成新的子集\n",
    "            res += [curr + [i] for curr in res]\n",
    "            # 返回结果列表\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = [[]] \n",
    "        for c in nums:\n",
    "            newres = []\n",
    "            for m in res:\n",
    "                newres.append(m+[c])\n",
    "            res += newres\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[],]\n",
    "        if not nums:\n",
    "            return res            \n",
    "        for num in nums:\n",
    "            res += [arr+[num] for arr in res]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\n",
    "        res = [[]]\n",
    "        for num in nums:\n",
    "            res += [_ + [num] for _ in res]\n",
    "        return res\n",
    "\n",
    "\n",
    "        # each iteration in res for [1, 2, 3]\n",
    "        # num = 1, res = []\n",
    "        # []\n",
    "        # [1] \n",
    "        # num = 2, res = [], [1]\n",
    "        # [2]\n",
    "        # [1, 2]\n",
    "        # num = 3, res = [], [1], [2], [1, 2]\n",
    "        # [3]\n",
    "        # [1, 3]\n",
    "        # [2, 3]\n",
    "        # [1, 2, 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)   \n",
    "        res = []\n",
    "        c = []\n",
    "        def dfs(i: int = 0):\n",
    "            if i == n:\n",
    "                res.append(c[:])\n",
    "                return\n",
    "            c.append(nums[i])\n",
    "            dfs(i + 1)\n",
    "            c.pop()\n",
    "            dfs(i + 1)\n",
    "        dfs()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        # res = [[],]\n",
    "        # if not nums:\n",
    "        #     return res\n",
    "        # for num in nums:\n",
    "        #     res += [arr+[num] for arr in res]\n",
    "        # return res\n",
    "        ans = []\n",
    "        for i in range((1<<len(nums))):\n",
    "            temp = []\n",
    "            # print(i)\n",
    "            for j in range(len(nums)):\n",
    "                if i &(1<<j):\n",
    "                    temp.append(nums[j])\n",
    "            ans.append(temp)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        t = []\n",
    "        n = len(nums)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                res.append(t[:])\n",
    "                return\n",
    "            dfs(i + 1)\n",
    "            t.append(nums[i])\n",
    "            dfs(i + 1)\n",
    "            t.pop()\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\n",
    "        res = [[]]\n",
    "        for num in nums:\n",
    "            res += [_ + [num] for _ in res]\n",
    "        return res\n",
    "\n",
    "\n",
    "        # each item in res for [1, 2, 3]\n",
    "        # num = 1, res = []\n",
    "        # []\n",
    "        # [1] \n",
    "        # num = 2, res = [], [1]\n",
    "        # [2]\n",
    "        # [1, 2]\n",
    "        # num = 3, res = [], [1], [2], [1, 2]\n",
    "        # [3]\n",
    "        # [1, 3]\n",
    "        # [2, 3]\n",
    "        # [1, 2, 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans=[[]]\n",
    "        for i in nums:ans=ans+[[i]+j for j in ans]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        results = []\n",
    "        def branch(cur_list, cur_res):\n",
    "            if len(cur_list) == 0:\n",
    "                results.append(cur_res)\n",
    "            else:\n",
    "                sub_list = list(cur_res)\n",
    "                sub_list.append(cur_list[0])\n",
    "                del cur_list[0]\n",
    "                left_list1 = list(cur_list)\n",
    "                left_list2 = list(cur_list)\n",
    "                branch(left_list1, sub_list)\n",
    "                sub_list2 = list(cur_res)\n",
    "                branch(left_list2, sub_list2)\n",
    "        begin_list = []\n",
    "        branch(nums, begin_list)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        def backtrack(nums, path):\n",
    "            res.append(path)\n",
    "            if nums == []:\n",
    "                return \n",
    "            for i in range(len(nums)):\n",
    "                backtrack(nums[i+1:] , path + [nums[i]])\n",
    "        backtrack(nums, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[],]\n",
    "        if not nums:\n",
    "            return res\n",
    "        for num in nums:\n",
    "            res += [arr+[num] for arr in res]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        if not nums:\n",
    "            return res\n",
    "\n",
    "        for num in nums:\n",
    "            res += [arr + [num] for arr in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res,stk,n=[],[],len(nums)\n",
    "        def dfs(u):\n",
    "            if(u==n):res.append(stk[:]);return\n",
    "            dfs(u+1)\n",
    "            stk.append(nums[u]);dfs(u+1);del stk[-1]\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "        def dfs(i: int) -> None:\n",
    "            ans.append(path.copy())  # 复制 path\n",
    "            if i == n:\n",
    "                return\n",
    "            for j in range(i, n):  # 枚举选择的数字\n",
    "                path.append(nums[j])\n",
    "                dfs(j + 1)\n",
    "                path.pop()  # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        result = [[]]\n",
    "        for i in range(n):\n",
    "            m = len(result)\n",
    "            for j in range(m):\n",
    "                result.append(result[j] + [nums[i]])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = [[]]\n",
    "        n = len(nums)\n",
    "        for i in range(1,n+1):\n",
    "            ans.extend([list(tp) for tp in combinations(nums,i)])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(bin(pow(2,len(nums))-1))-2\n",
    "        for i in range(pow(2,len(nums))):\n",
    "            num = bin(i)[2:]\n",
    "            while len(num) < n:\n",
    "                num = \"0\" + num\n",
    "            arr = []\n",
    "            for j in range(n):\n",
    "                if num[j]==\"1\":\n",
    "                    arr.append(nums[j])\n",
    "            ans.append(arr)\n",
    "            # print(arr)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[],]\n",
    "        if not nums:\n",
    "            return res\n",
    "            \n",
    "        for num in nums:\n",
    "            res += [arr+[num] for arr in res]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(path, startIndex, nums, ans):\n",
    "            ans.append(path[:])\n",
    "            for i in range(startIndex, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                dfs(path, i + 1, nums, ans)\n",
    "                path.pop()\n",
    "            return ans\n",
    "        return dfs([], 0, nums, [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: list[int]) -> list[list[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        tmp = []\n",
    "        for i in range(0, pow(2, n)):\n",
    "            a = str(bin(i))\n",
    "            a = a[2:]\n",
    "            a=a.zfill(n)\n",
    "            tmp.append(a)\n",
    "            \n",
    "        ans = []\n",
    "        # print(tmp)\n",
    "        for i in tmp:\n",
    "            t = []\n",
    "            for j in range(0, len(i)):\n",
    "                if i[j] == \"1\":\n",
    "                    t.append(nums[j])\n",
    "            ans.append(t)\n",
    "        return ans\n",
    "\n",
    "\n",
    "# exmp = Solution()\n",
    "# print(exmp.subsets([1, 2, 3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        for i in nums:\n",
    "            n = len(res)\n",
    "            for j in range(n):\n",
    "                new = res[j][:]\n",
    "                new.append(i)\n",
    "                res.append(new)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "\n",
    "        def dfs(i: int):\n",
    "            if i == n:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            dfs(i + 1)\n",
    "            path.append(nums[i])\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def backtracing(subset: List, res: List[List], cur_idx) -> None:\n",
    "            res.append(list(subset))\n",
    "\n",
    "            if cur_idx > len(nums)-1:\n",
    "                return \n",
    "            \n",
    "            for i in range(cur_idx, len(nums)):\n",
    "                subset.append(nums[i])\n",
    "                backtracing(subset, res, i+1)\n",
    "                subset.pop()\n",
    "        \n",
    "        res = []\n",
    "        backtracing([], res, 0)\n",
    "        # print(res)\n",
    "        return res \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def backtracing(subset: List, res: List[List], cur_idx) -> None:\n",
    "            res.append(list(subset))\n",
    "\n",
    "            if cur_idx > len(nums)-1:\n",
    "                return \n",
    "            \n",
    "            for i in range(cur_idx, len(nums)):\n",
    "                subset.append(nums[i])\n",
    "                backtracing(subset, res, i+1)\n",
    "                subset.pop()\n",
    "        \n",
    "        res = []\n",
    "        backtracing([], res, 0)\n",
    "        # print(res)\n",
    "        return res \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        self.dfs([], nums, 0, res)\n",
    "        return res\n",
    "    def dfs(self, path, nums, pos, res):\n",
    "        if pos >= len(nums):\n",
    "            res.append(path[:])\n",
    "            return\n",
    "        path.append(nums[pos])\n",
    "        self.dfs(path, nums, pos+1, res)\n",
    "        path.pop()\n",
    "        self.dfs(path, nums, pos+1, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = [[]] \n",
    "        for c in nums:\n",
    "            newres = []\n",
    "            for m in res:\n",
    "                newres.append(m+[c])\n",
    "            res += newres\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        path=[]\n",
    "        n=len(nums)\n",
    "        def dfs(i:int):\n",
    "            ans.append(path.copy())\n",
    "            if i == n:\n",
    "                return \n",
    "            for j in range(i,n):\n",
    "                path.append(nums[j])\n",
    "                dfs(j+1)\n",
    "                path.pop() #中间量\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        dp = collections.defaultdict(list)\n",
    "        dp[0].append([nums[0]])\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            # 1. append self to dp\n",
    "            dp[i].append([nums[i]])\n",
    "            # 2. extend all prev 1 level subsets\n",
    "            dp[i].extend(dp[i-1])\n",
    "            # 3. append self to all prev 1 level subsets \n",
    "            for l in dp[i-1]:\n",
    "                dp[i].append(l + [nums[i]])\n",
    "        \n",
    "        res.extend(dp[n-1])\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "      def backtrace(start,temp):\n",
    "        res.append(temp[:])\n",
    "        for i in range(start,len(nums)):\n",
    "          temp.append(nums[i])\n",
    "          backtrace(i+1,temp)\n",
    "          temp.pop()\n",
    "      res=[]\n",
    "      backtrace(0,[])\n",
    "      \n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "        def dfs(i):\n",
    "            ans.append(path.copy())\n",
    "            if i == n:\n",
    "                return\n",
    "            for j in range(i,n):\n",
    "                path.append(nums[j])\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        def huisu(n,k,stratindex):\n",
    "            res.append(path.copy())\n",
    "            for i in range(stratindex,len(nums)):\n",
    "                path.append(nums[i])\n",
    "                huisu(nums,path,i+1)\n",
    "                path.pop()\n",
    "        res=[]\n",
    "        path=[]\n",
    "        huisu(nums,[],0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        resultList = [[]]\n",
    "        tempList = []\n",
    "        for j in nums:\n",
    "            resultList.append([j])\n",
    "\n",
    "        def backtrack(startI, resultList, nums, tempList, MaxtempListlen):\n",
    "            if len(tempList) == MaxtempListlen:\n",
    "                resultList+=[tempList]\n",
    "                return\n",
    "            elif len(tempList) < MaxtempListlen:\n",
    "                for i in range(startI, len(nums)+1 - (MaxtempListlen - len(tempList))):\n",
    "                    tempList=tempList+[nums[i]]\n",
    "                    backtrack(i + 1, resultList, nums, tempList, MaxtempListlen)\n",
    "                    tempList=tempList[0:len(tempList)-1]\n",
    "\n",
    "        for MaxtempListlen in range(2, len(nums) + 1):\n",
    "            backtrack(0, resultList, nums, tempList, MaxtempListlen)\n",
    "        return resultList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            curr_length = len(res)\n",
    "            for j in range(curr_length):\n",
    "                res.append(res[j] + [nums[i]])\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 全排列 存在重复数字的全排列\n",
    "        def backtracking(index):\n",
    "            if index == len(nums):\n",
    "                # final_path.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for i in range(index,len(nums)):\n",
    "                path.append(nums[i])\n",
    "                final_path.append(path[:])\n",
    "                backtracking(i+1)\n",
    "                path.pop()\n",
    "        \n",
    "        path = []\n",
    "        final_path = [[]]\n",
    "     \n",
    "        backtracking(0)\n",
    "        return final_path\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        res = []\n",
    "        path = deque()\n",
    "\n",
    "        def dfs(i):\n",
    "            # 幂集，无条件收集\n",
    "            res.append(list(path))\n",
    "            if i == n:\n",
    "                return\n",
    "            # 枚举选择的数字\n",
    "            for j in range(i, n):\n",
    "                path.append(nums[j])\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(path,startcindex):\n",
    "            res.append(path[:])\n",
    "            for i in range(startcindex,len(nums)):\n",
    "                path.append(nums[i])\n",
    "                dfs(path,i+1)\n",
    "                path.pop()\n",
    "        dfs([],0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = list()\n",
    "        s = list()\n",
    "        \n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                res.append(s.copy())\n",
    "                return\n",
    "            \n",
    "            s.append(nums[i])\n",
    "            dfs(i-1)\n",
    "            s.pop()\n",
    "\n",
    "            dfs(i-1)\n",
    "        \n",
    "        dfs(n-1)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums) == 0:\n",
    "            return [[]]\n",
    "        sub_sets = self.subsets(nums[1:])\n",
    "        ans = list()\n",
    "        for sub_set in sub_sets:\n",
    "            ans.append([nums[0]] + sub_set)\n",
    "        ans += sub_sets\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
